Chứng minh Định_lý_Helly

Ta chứng minh phiên bản hữu hạn của định lý thông qua định lý Radon như trong chứng minh của Radon (1921)Lỗi harv: không có mục tiêu: CITEREFRadon1921 (trợ giúp). Từ đó ta có phiên bản vô hạn thông qua tính chất giao hữu hạn của không gian compact: giao của một gia đình các tập hợp là khác rỗng khi và chỉ khi mọi bộ hữu hạn các tập trong gia đình đó có giao khác rỗng.

Trước hết giả sử n = d + 2 {\displaystyle n=d+2} . Theo giả thuyết của định lý, tồn tại điểm x 1 {\displaystyle x_{1}} nằm trong giao của

X 2 , X 3 , … , X n . {\displaystyle X_{2},X_{3},\dots ,X_{n}.}

Tương tự như vậy, với mọi

j = 2 , 3 , … , n {\displaystyle j=2,3,\dots ,n}

tồn tại điểm x j {\displaystyle x_{j}} nằm trong giao của mọi X i {\displaystyle X_{i}} ngoại trừ X j {\displaystyle X_{j}} .Ta áp dụng định lý Radon cho tập

A = { x 1 , x 2 , … , x n } . {\displaystyle A=\{x_{1},x_{2},\dots ,x_{n}\}.}

Theo định lý Radon, tồn tại hai tập hợp không giao nhau A 1 , A 2 ⊂ A {\displaystyle A_{1},A_{2}\subset A} sao cho bao lồi của A 1 {\displaystyle A_{1}} giao với bao lồi của A 2 {\displaystyle A_{2}} . Giả sử p {\displaystyle p} là điểm nằm trong phần giao của hai bao lồi. Ta sẽ chứng minh

p ∈ ⋂ j = 1 n X j . {\displaystyle p\in \bigcap _{j=1}^{n}X_{j}.}

Thật vậy, xét j ∈ { 1 , 2 , . . . , n } {\displaystyle j\in \{1,2,...,n\}} bất kì. Phần tử duy nhất trong A {\displaystyle A} có thể không nằm trong X j {\displaystyle X_{j}} là x j {\displaystyle x_{j}} . Nếu x j ∈ A 1 {\displaystyle x_{j}\in A_{1}} , thì x j ∉ A 2 {\displaystyle x_{j}\notin A_{2}} , và do đó X j ⊃ A 2 {\displaystyle X_{j}\supset A_{2}} .Do X j {\displaystyle X_{j}} lồi, nó cũng chứa bao lồi của A 2 {\displaystyle A_{2}} và do đó p ∈ X j {\displaystyle p\in X_{j}} .Tương tự như vậy, nếu x j ∉ A 1 {\displaystyle x_{j}\notin A_{1}} , thì X j ⊃ A 1 {\displaystyle X_{j}\supset A_{1}} , và lập luận tương tự như trên, ta có p ∈ X j {\displaystyle p\in X_{j}} .Do p {\displaystyle p} nằm trong mọi X j {\displaystyle X_{j}} , nó nằm trong giao của chúng.

Ở trên ta giả sử x 1 , x 2 , … , x n {\displaystyle x_{1},x_{2},\dots ,x_{n}} là các điểm khác nhau. Nếu điều này không đúng, chẳng hạn x i = x k {\displaystyle x_{i}=x_{k}} cho hai số i ≠ k {\displaystyle i\neq k} nào đó, thì x i {\displaystyle x_{i}} nằm trong mọi tập X j {\displaystyle X_{j}} , và ta cũng kết luận giao của tất cả các tập hợp là khác rỗng. Như vậy ta đã chứng minh được định lý cho trường hợp n = d + 2 {\displaystyle n=d+2} .

Giả sử n > d + 2 {\displaystyle n>d+2} và ta có giả thiết quy nạp là định lý đúng cho n − 1 {\displaystyle n-1} .Chứng minh trên cho thấy mọi bộ d + 2 {\displaystyle d+2} tập có giao khác rỗng.Ta xét một gia đình các tập hợp mới trong đó X n − 1 {\displaystyle X_{n-1}} và X n {\displaystyle X_{n}} được thay bằng

X n − 1 ∩ X n . {\displaystyle X_{n-1}\cap X_{n}.}

Trong gia đình mới này, giao của mọi bộ d + 1 {\displaystyle d+1} tập là khác rỗng. Theo giả thiết quy nạp, giao của tất cả các tập hợp mới là khác rỗng. Do đó, giao của tất cả các tập hợp ban đầu cũng khác rỗng.